#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : MinimumNumberArrowsBurstBalloons.py
# @Time    : 2020/11/23 10:15
# @Description:
from typing import List


class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        """
        There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the
        start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter,
        and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end.

        An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart
        and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that
        can be shot. An arrow once shot keeps traveling up infinitely.

        Given an array points where points[i] = [xstart, xend], return the minimum number of arrows that must be
        shot to burst all balloons.

        Example 1:
            Input: points = [[10,16],[2,8],[1,6],[7,12]]
            Output: 2
            Explanation: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6])
            and another arrow at x = 11 (bursting the other two balloons).
        Example 2:
            Input: points = [[1,2],[3,4],[5,6],[7,8]]
            Output: 4
        Example 3:
            Input: points = [[1,2],[2,3],[3,4],[4,5]]
            Output: 2
        Example 4:
            Input: points = [[1,2]]
            Output: 1
        Example 5:
            Input: points = [[2,3],[2,3]]
            Output: 1

        Constraints:
            - 0 <= points.length <= 104
            - points[i].length == 2
            - -231 <= xstart < xend <= 231 - 1

        :param points:
        :return:
        """
        if not points:
            return 0

        points.sort(key=lambda ballon: ballon[1])
        pos = points[0][1]
        ans = 1
        for ballon in points:
            if ballon[0] > pos:
                pos = ballon[1]
                ans += 1
        return ans


if __name__ == '__main__':
    S = Solution()
    points = [[10, 16], [2, 8], [1, 6], [7, 12]]
    print(S.findMinArrowShots(points))
    print('done')
